package com.leetcode.根据数据结构分类.并查集;

import java.util.*;

/**
 * @author: xiaomi
 * @date: 2021/1/31
 * @description: 778. 水位上升的泳池中游泳
 * https://leetcode-cn.com/problems/swim-in-rising-water/
 */
public class C_778_水位上升的泳池中游泳 {
	public static void main(String[] args) {
		int[][] grid = {{0, 1, 2, 3, 4}, {24, 23, 22, 21, 5}, {12, 13, 14, 15, 16}, {11, 17, 18, 19, 20}, {10, 9, 8, 7, 6}};

		C_778_水位上升的泳池中游泳 action = new C_778_水位上升的泳池中游泳();
		int res = action.swimInWater(grid);
		System.out.println("res = " + res);
	}

	/**
	 * 1.建模：将 (0,0) 的位置置为标准 0，将其他的位置的值相应减去 grid[0][0] 的值。
	 * 此时可以将--此路不通
	 * --
	 * 上述建模错误，因为后面我就不知道怎么走了。
	 * 1.重新建模：由于从 (0,0) 到 （m-1,n-1）,所以令往左/下为正方向，每个格子都视为顶点
	 * --
	 * 还是建不出来
	 * 1.对每个网格进行顶点建模；并遍历放入 Heap 中；
	 * 2.以此弹出堆，每一个弹出的元素属性设置为 true,把每一次弹出的网格与上下左右四个方向进行 check if active
	 * and union
	 * 真是丝滑的思路。我真厉害。
	 * 后面还有一些其他的解体思路：二分查找 + 遍历|Dijkstra
	 * @param grid
	 * @return
	 */
	public int swimInWater(int[][] grid) {
		//行
		int m = grid.length;
		//列
		int n = grid[0].length;
		int size = m * n;
		B_1631_最小体力消耗路径.InnerUnionFind unionFind = new B_1631_最小体力消耗路径.InnerUnionFind(size);
		int endIndex = size - 1;
		PriorityQueue<Point> heap = new PriorityQueue<>(new Comparator<Point>() {
			@Override
			public int compare(Point o1, Point o2) {
				return o1.value - o2.value;
			}
		});
		//创建一个 Point 数组，存放结构转换之后的 grid
		Point[] pointsArr = new Point[size];
		for (int i = 0, index = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				Point point = new Point(index, grid[i][j]);
				pointsArr[index++] = point;
				heap.offer(point);
			}
		}
		//此时已经完成入栈
		int res = 0;
		Point curPoint;
		Point up, down, left, right;
		int lastRowIndex = size - n;
		int remainderValue = n - 1;
		while (!unionFind.isSame(0, endIndex)) {
			//弹出最小的 顶点
			curPoint = heap.poll();
			//激活该顶点
			curPoint.isActive = true;
			//寻找周围的顶点，如果存在 isActive -> 合并
			//需要一个快速合并的结构
			//1.处理与上格子的合并
			if (curPoint.index >= n) {
				//说明有上格子
				up = pointsArr[curPoint.index - n];
				if (up.isActive) {
					unionFind.union(up.index, curPoint.index);
				}
			}
			//2.处理与下格子的合并
			if (curPoint.index < lastRowIndex) {
				//说明有下格子
				down = pointsArr[curPoint.index + n];
				if (down.isActive) {
					unionFind.union(down.index, curPoint.index);
				}
			}
			//计算余数
			int temp = curPoint.index % n;
			//3.处理与左格子的合并
			if (temp != 0) {
				//说明有左格子
				left = pointsArr[curPoint.index - 1];
				if (left.isActive) {
					unionFind.union(left.index, curPoint.index);
				}
			}
			//4.处理与右格子的合并
			if (temp != remainderValue) {
				//说明有右格子
				right = pointsArr[curPoint.index + 1];
				if (right.isActive) {
					unionFind.union(right.index, curPoint.index);
				}
			}

			res = curPoint.value;
		}
		return res;


	}

	private int[][] initPool(int[][] grid, int m, int n) {
		int[][] pool = new int[m][n];
		int value = grid[0][0];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				pool[i][j] = grid[i][j] - value;
			}
		}
		return pool;
	}

	/**
	 * 无向边
	 */
	static class Edge {
		Set<Integer> points = new HashSet<>();
		int value;

		public Edge(int point1, int point2, int value) {
			points.add(point1);
			points.add(point2);
			this.value = value;
		}
	}

	/**
	 * 顶点
	 */
	static class Point {
		public int value;
		public int index;
		public boolean isActive;

		public Point(int index, int value) {
			this.index = index;
			this.value = value;
			this.isActive = false;
		}
	}


}


